/*
题目: 找到所有的好下标
给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。

对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：

    下标 i 之前 的 k 个元素是 非递增的 。
    下标 i 之后 的 k 个元素是 非递减的 。

按 升序 返回所有好下标。

https://leetcode.cn/contest/weekly-contest-312/problems/find-all-good-indices/
 */
public class GoodIndices {
    List<Integer> src = new ArrayList<> ();

    public List<Integer> goodIndices(int[] nums, int k) {
        // 预处理一下
        int n = nums.length;
        // 表示 i 下标 前  down[i] 个元素 都是递减的
        int[] down = new int[n];
        int cnt = 1;
        down[1] = 1;
        for (int i = 1; i < n - k - 1; i ++) {
            if (nums[i - 1] >= nums[i]) {
                cnt ++;
            } else {
                cnt = 1;
            }
            down[i + 1] = cnt;
        }

        int[] up = new int[n];
        up[n - 2] = 1;
        for (int i = n - 2; i > k; i --) {
            if (nums[i] <= nums[i + 1]) {
                cnt ++;
            } else {
                cnt = 1;
            }
            up[i - 1] = cnt; // 每轮循环都是服务于 ves[index + 1];
        }

        for (int i = k; i < n - k; i ++) {
            if (down[i] >= k && up[i] >= k) {
                src.add(i);
            }
        }

        return src;
    }
}
